package 回文串;

public class test1 {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int count =0;
        for (int i=n-1;i>=0;i--){
            for (int j = i; j < n; j++) {
                // i<=j
                if(s.charAt(i)==s.charAt(j))
                    dp[i][j] =i+1<j?dp[i+1][j-1]:true;
                else
                    dp[i][j] = false;
                if(dp[i][j])
                    count++;
            }
        }
        return count;
    }
}
